#include "heap.h"

using std::cout;
using std::endl;

void test1()
{
    Heap<int> heap;
    heap.push(1);
    heap.push(2);
    heap.push(3);
    heap.push(4);
    heap.push(5);
    heap.push(6);

    heap.foreach();

    heap.pop();
    heap.foreach();
    heap.pop();
    heap.foreach();
    heap.pop();

    heap.foreach();
    heap.push(10);
    heap.foreach();
}

void shiftDown(vector<int> &vec, int rootIdx, int end)
{
    int val = vec[rootIdx];
    while(rootIdx <= (end - 1) / 2){
        int child = rootIdx * 2 + 1;
        if(child + 1 <= end && vec[child + 1] > vec[child]){
            child = child + 1;
        }
        if(vec[child] > val){
            vec[rootIdx] = vec[child];
            rootIdx = child;
        }else{
            break;
        }
    }

    vec[rootIdx] = val;
}

void heapSort(vector<int> &vec)
{
    for(int root = vec.size() / 2 - 1; root >= 0; root--){
        shiftDown(vec, root, vec.size() - 1);
    }

    for(int len {vec.size() - 1}; len > 0; len--){
        int tmp = vec[0];
        vec[0] = vec[len];
        vec[len] = tmp;
        shiftDown(vec, 0, len - 1);
    }

    for(int i: vec){
        cout << i << " ";
    }
    cout << endl;

}

int main(int args, char *argv[])
{
    // test1();
    vector<int> vec{9, 4, 1, 3, 5, 4, 1, 6};
    heapSort(vec);
    return 0;
}